// https://leetcode.cn/problems/next-greater-element-i/description/

// 算法思路总结：
// 1. 单调栈求解下一个更大元素
// 2. 逆序遍历维护递减栈结构
// 3. 栈顶元素即为当前元素的下一个更大值
// 4. 哈希表记录映射关系快速查询
// 5. 时间复杂度：O(m+n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <unordered_map>
#include <stack>

class Solution 
{
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) 
    {
        stack<int> st;
        unordered_map<int, int> nextGreater;

        for (int i = nums2.size() - 1 ; i >= 0 ; i--)
        {
            while (!st.empty() && nums2[i] >= st.top())
            {
                st.pop();
            }
            nextGreater[nums2[i]] = st.empty() ? -1 : st.top();
            st.push(nums2[i]);
        }

        vector<int> ret;
        for (const int& num : nums1)
        {
            ret.push_back(nextGreater[num]);
        }

        return ret;
    } 
};

int main()
{
    Solution sol;

    vector<int> nums11 = {4,1,2}, nums12 = {1,3,4,2};
    vector<int> nums21 = {2,4}, nums22 = {1,2,3,4};

    auto v1 = sol.nextGreaterElement(nums11, nums12);
    auto v2 = sol.nextGreaterElement(nums21, nums22);

    for (const int& num : v1)
        cout << num << " ";
    cout << endl;

    for (const int& num : v2)
        cout << num << " ";
    cout << endl;

    return 0;
}